﻿#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <stack>
#include <map>
#include <string>
#include <functional>
using namespace std;
//力扣习题：逆波兰表达式求值
// 给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

//请你计算该表达式。返回一个表示表达式值的整数。
//
//注意：
//
//有效的算符为 '+'、'-'、'*' 和 '/' 。
//每个操作数（运算对象）都可以是一个整数或者另一个表达式。
//两个整数之间的除法总是 向零截断 。
//表达式中不含除零运算。
//输入是一个根据逆波兰表示法表示的算术表达式。
//答案及所有中间计算结果可以用 32 位 整数表示。
// 
// https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/
//传统方法：栈
// class Solution 
//{
// public:
//     int evalRPN(vector<string>& tokens) 
//     {
//         stack<int> st;
//         for(auto& str:tokens)
//         {
//             if(str=="+"||str=="-"||str=="*"||str=="/")
//             {
//                 //遇到运算符要出栈两个运算数然后运算后入栈
//                 int right=st.top();
//                 st.pop();
//                 int left=st.top();
//                 st.pop();
//                 switch(str[0])
//                 {
//                     case '+':
//                     st.push(left+right);
//                     break;

//                     case '-':
//                     st.push(left-right);
//                     break;
//                     case '*':
//                     st.push(left*right);
//                     break;
//                     case '/':
//                     st.push(left/right);
//                     break;
//                     default:
//                     break;
//                 }
//             }
//             else
//             {
//                 //运算数入栈
//                 st.push(stoi(str));
//             }
//         }        
//         return st.top();
//     }
// };
// 使⽤map映射string和function的⽅式实现
// 这种⽅式的最⼤优势之⼀是⽅便扩展，假设还有其他运算，我们增加map中的映射即可
class Solution
{
public:
    int evalRPN(vector<string>& tokens)
    {
        stack<int> st;
        // function作为map的映射可调⽤对象的类型
        map<string, function<int(int, int)>> opFuncMap = {
            {"+", [](int x, int y) {return x + y; }},
            {"-", [](int x, int y) {return x - y; }},
            {"*", [](int x, int y) {return x * y; }},
            {"/", [](int x, int y) {return x / y; }}
        };
        for (auto& str : tokens)
        {
            if (opFuncMap.count(str)) // 操作符
            {
                int right = st.top();
                st.pop();
                int left = st.top();
                st.pop();
                int ret = opFuncMap[str](left, right);
                st.push(ret);
            }
            else
            {
                st.push(stoi(str));
            }
        }
        return st.top();
    }
};